package com.eatme.core.sort;

import com.eatme.core.array.ArrayGenerator;

import java.util.Arrays;

public class MergeSortV1 {

    private MergeSortV1() {

    }

    // 自顶向下的归并排序
    public static <E extends  Comparable<E>> void sort(E[] arr) {
        E[] temp = Arrays.copyOf(arr,arr.length);
        sort(arr,0, arr.length-1,temp);
    }

    private static  <E extends  Comparable> void sort(E[] arr,int l,int r,E[] temp){
        if (l>=r) return;
        int mid =l+(r-l)/2; // 防止溢出
        sort(arr,l,mid,temp);
        sort(arr,mid+1,r,temp);
        if (arr[mid].compareTo(arr[mid+1]) > 0)
            merge(arr,l,mid,r,temp);
    }

    public static <E extends  Comparable<E>> void sortV4(E[] arr) {
        sortV4(arr,0, arr.length-1);
    }

    private static  <E extends  Comparable> void sortV4(E[] arr,int l,int r){
        if (l>=r) return;
        int mid =l+(r-l)/2; // 防止溢出
        sortV4(arr,l,mid);
        sortV4(arr,mid+1,r);

        if (arr[mid].compareTo(arr[mid+1]) > 0)
            merge(arr,l,mid,r);
    }

    public static <E extends  Comparable<E>> void sortV3(E[] arr) {
        sortV3(arr,0, arr.length-1);
    }

    private static  <E extends  Comparable> void sortV3(E[] arr,int l,int r){

        //if (l>=r) return;

        // 是否会提升效率？
        if (r-l <= 15) {
            InsertionSort.sort(arr,l,r);
            return;
        }

        int mid =l+(r-l)/2; // 防止溢出
        sortV3(arr,l,mid);
        sortV3(arr,mid+1,r);

        if (arr[mid].compareTo(arr[mid+1]) > 0)
            merge(arr,l,mid,r);
    }

    public static <E extends  Comparable<E>> void sortV2(E[] arr) {
        sortV2(arr,0, arr.length-1);
    }

    private static  <E extends  Comparable> void sortV2(E[] arr,int l,int r){
        if (l>=r) return;
        int mid =l+(r-l)/2; // 防止溢出
        sortV2(arr,l,mid);
        sortV2(arr,mid+1,r);
        merge(arr,l,mid,r);
    }
    // 合并两个有序的区间arr[l...mid] 和 arr[mid+1,r]
    private static <E extends Comparable> void merge(E[] arr,int l,int mid,int r,E[] temp) {
        System.arraycopy(arr,l,temp,l,r-l+1);
        int i= l, j = mid+1;
        // 每轮循环为arr[k] 赋值
        for (int k = l; k<=r; k++) {

            // arr[i] 和 arr[j]
            if (i>mid) {
                arr[k] = temp[j];
                j++;
            }else if (j>r) {
                arr[k] =temp[i];
                i++;
            }else if (temp[i].compareTo(temp[j])<=0) {
                arr[k] =temp[i];
                i++;
            }else {
                arr[k] = temp[j];
                j++;
            }
        }
    }





    // 合并两个有序的区间arr[l...mid] 和 arr[mid+1,r]
    private static <E extends Comparable> void merge(E[] arr,int l,int mid,int r) {
        E [] temp = Arrays.copyOfRange(arr,l,r+1);
        int i= l, j = mid+1;
        // 每轮循环为arr[k] 赋值
        for (int k = l; k<=r; k++) {

            // arr[i] 和 arr[j]
            if (i>mid) {
                arr[k] = temp[j-l];
                j++;
            }else if (j>r) {
                arr[k] =temp[i-l];
                i++;
            }else if (temp[i-l].compareTo(temp[j-l])<=0) {
                arr[k] =temp[i-l];
                i++;
            }else {
                arr[k] = temp[j-l];
                j++;
            }
        }
    }

    public static void main(String[] args) {

        int n = 100000;

        System.out.println("RandomArray");
        Integer[] arr =ArrayGenerator.generateRandomArray(n,n);
        Integer[] arr2 = Arrays.copyOf(arr,arr.length);
        Integer[] arr3 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_1 = Arrays.copyOf(arr,arr.length);
        Integer[] arr4_2 = Arrays.copyOf(arr,arr.length);

        SortingHelper.sortTest("MergeSort",arr);
        SortingHelper.sortTest("MergeSortV2",arr4);
        SortingHelper.sortTest("MergeSortV3",arr4_1);
        SortingHelper.sortTest("MergeSortV4",arr4_2);
        //SortingHelper.sortTest("SelectionSort",arr2);
        //SortingHelper.sortTest("InsertionSort",arr3);


        System.out.println("OrderedArray");
        Integer[] arr5 =ArrayGenerator.generateOrderedArray(n);
        Integer[] arr6 = Arrays.copyOf(arr5,arr.length);
        Integer[] arr6_1 = Arrays.copyOf(arr5,arr.length);
        Integer[] arr6_2 = Arrays.copyOf(arr5,arr.length);
        Integer[] arr7 = Arrays.copyOf(arr5,arr.length);
        Integer[] arr8 = Arrays.copyOf(arr5,arr.length);

        SortingHelper.sortTest("MergeSort",arr5);
        SortingHelper.sortTest("MergeSortV2",arr6);
        SortingHelper.sortTest("MergeSortV3",arr6_1);
        SortingHelper.sortTest("MergeSortV4",arr6_2);
        //SortingHelper.sortTest("SelectionSort",arr7);
        //SortingHelper.sortTest("InsertionSort",arr8);

    }




}
